package leetcode_day._2022._202210._1120;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 769. 最多能完成排序的块
 * 算法：模拟、栈
 * 找到每个块中最大的那个数
 * 因为 arr 的范围为 [0, n - 1] 并且元素不重复,
 * 所以如果最大值 = 下标, 则这个最大值就是这个块的最大值
 *
 * @author yzh
 * @version 1.0
 * @date 2022/10/13 21:43
 */
public class _13_769 {

    public int maxChunksToSorted(int[] arr) {
        int ans = 0, n = arr.length;
        for (int i = 0, max = -1; i < n; i++) {
            max = Math.max(max, arr[i]);
            if (max == i) ++ans;
        }
        return ans;
    }

    public int maxChunksToSorted_stack(int[] arr) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (int item : arr) {
            if (stack.isEmpty()) stack.addLast(item);
            else if (item > stack.peekLast()) stack.addLast(item);
            else {
                int top = stack.pollLast();
                while (!stack.isEmpty() && item < stack.peekLast()) stack.pollLast();
                stack.addLast(top);
            }
        }
        return stack.size();
    }

}
